const { buildBinaryTree, consoleTree } = require('../tools');

// Morris遍历: 遍历过程中计算后继指针, 这样可以不用使用栈, 其空间复杂度可以达到O(1)

/**
 * 中序遍历 left mid right
 * node.left == null -> node = node.right
 * node.left != null -> 在node的左子树中找到其前驱节点p
 *   p.right == null -> p.right = node; node = node.left;
 *   p.right != null -> 即p指向node, node的左子树已经遍历完成, p.right = null; node = node.right
 */
const MorrisInOrderTraversal = (node) => {
  const ans = [];
  let cur = node;
  while (cur) {
    if (cur.left) {
      let p = cur.left;
      while(p.right && p.right != cur) {
        p = p.right;
      }
      if (!p.right) {
        p.right = cur;
        cur = cur.left;
        continue;
      } else {
        p.right = null;
      }
    }
    ans.push(cur.val);
    cur = cur.right; 
  }
  return ans;
}

/**
 * 前序遍历 mid left right
 * node.left == null -> node = node.right
 * node.left != null -> 在node的左子树中找到其前驱节点p
 *   p.right == null -> p.right = node; 输出p节点; node = node.left
 *   p.right != null -> 即p指向node, node的左子树已经遍历完成, p.right = null; node = node.right
 */
const MorrisPreOrderTraversal = (node) => {
  let cur = node;
  const ans = [];
  while (cur) {
    if (cur.left) {
      let p = cur.left;
      // 计算cur的前驱节点
      while (p.right && p.right !== cur) {
        p = p.right;
      }
      if (!p.right) {
        ans.push(cur.val);
        p.right = cur;
        cur = cur.left;
        continue
      }
      // p指向当前节点
      p.right = null;
    } else {
      ans.push(cur.val);
    }
    cur = cur.right;
  }
  return ans;
};

/**
 * 后序遍历 left right mid
 * node.left == null -> node = node.right
 * node.left != null -> 在node的左子树中找到其前驱节点p
 *   p.right == null -> p.right = node; 输出p节点; 
 *   p.right != null -> 即p指向node, node的左子树已经遍历完成, p.right = null; node = node.right
 */


const tree = buildBinaryTree([1, 2, 3, 4, 5, 6, 7]);
consoleTree(tree);
// const InOrder = MorrisInOrderTraversal(tree);
// console.log('InOrder Array:', InOrder);
const PreOrder = MorrisPreOrderTraversal(tree);
console.log('PreOrder Array:', PreOrder);